/*
 * Copyright (c) 2022  by Junzhao
 * THIS FILE IS PART OF JAVA-Data-Structures-and-Algorithms PROJECT
 * All Rights Reserved.
 */

package 插值;

/**
 * @Description 插值查找
 * 根据查找关键字与查找表中
 * 最大最小记录关键字比较后的查找方法。
 * 插值查找基于二分查找(也是要求有序 且这里是升序)，
 * 将查找点的选择改进为 自 适 应 选择，提高查找效率。
 * 注意！
 * 对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找, 速度较快.
 * 关键字分布不均匀的情况下，该方法不一定比折半查找要好
 * @Author 俊昭
 * @Date 2022/5/2
 */
public class Interpolation {
    public static int search(int[] arr, int num) {
        return search(arr, num, 0, arr.length - 1);
    }

    private static int search(int[] arr, int num, int left, int right) {
        if (left > right || num < arr[0] || num > arr[arr.length - 1]) {
            return - 1;
        }
//        int mid = (left + right) / 2;这是二分查找的mid
//        int mid = (left + right) / 2 = left + （1/2)*(right-left);
        int k = (num - arr[left]) / (arr[right] - arr[left]);
        int mid = left + k * (right - left);
        while (left < right) {
            if (arr[mid] == num) {
                return mid;
            } else if (mid > num) {
                right = mid - 1;
                return search(arr, num, left, right);
            } else if (mid < num) {
                left = mid + 1;
                return search(arr, num, left, right);
            }
        }
        return - 1;
    }

}